package algorithm.search;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二分搜索树
 *
 * @author bingo
 * @create 2018-02-27 14:55
 **/
public class BinarySearchTree<Key extends Comparable<Key>,Value> {

    public class  Node{

        private Key key;

        private  Value value;

        private  Node left;

        private  Node right;

        public Node(Key key, Value value) {
            this.key=key;
            this.value=value;
            this.left=right = null;
        }

    }

    private int count;

    private  Node root;

    public BinarySearchTree() {
        this.count = 0;
        this.root = null;
    }

    public int  getSize(){

        return count;
    }

    public boolean isEmpty(){

        return  count==0;
    }


     /**查看是否包含某元素*/
     public boolean contain(Key key){

        return contain(root,key);

    }
     private boolean contain(Node node ,Key key){

        if(node==null){

            return  false;
        }

        if(key.compareTo(node.key) == 0){
            return  true;
        } else if(key.compareTo(node.key)<0){
          return   contain(node.left,key);
        } else{
            return contain(node.right,key);
        }

    }

    public Value  search(Key key){

      return    search(root,key);
    }
     /**查找包含某元素节点*/
    private Value search(Node node, Key key) {
        if(node==null){
            return  null;
        }

        if(node.key.compareTo(key) == 0){
            return node.value;
        } else if(node.key.compareTo(key)>0){
            return  search(node.left,key);
        } else{
            return  search(node.right,key);
        }
    }
    /**添加元素**/
    public void insert(Key key,Value value){

        root = insert(root ,key,value);

    }

    private Node insert(Node node, Key key, Value value) {
        if(node == null){
            count++;
            return  new Node(key,value);
        }
        if(key.compareTo(node.key) == 0){
            node.value=value;
        }
        else if(key.compareTo(node.key)<0){
            node.left =insert(node.left,key,value);
        }
        else{
            node.right = insert(node.right,key,value);
        }
        return  node;
    }
    public void set(Key key,Value value){

        Node  res = getNode(key);
        if(res==null){
            throw  new IllegalArgumentException("doesn't have key called"+key);
        }
        res.value = value;
    }

    public Value get(Key key){

        Node node = getNode(root,key);

        return  node==null ? null : node.value;
    }

    public Node getNode(Key key){

        return getNode(root,key);
    }

    private Node getNode(Node node, Key key) {

        if(node==null){
            return  null;
        }

        if(node.key.compareTo(key)==0){

            return  node;
        } else if(key.compareTo(node.key)>0){

            return  getNode(node.right,key);

        }
        else {
            return  getNode(node.left,key);
        }
    }

    /**先序遍历*/
    public void ahead(Node node){
        if(node!=null){
            System.out.println(node.key+","+node.value);
            ahead(node.left);
            ahead(node.right);

        }
    }
    /**中序遍历**/
    public void order(Node node){
        if(node!=null){
            order(node.left);
            System.out.println(node.key+","+node.value);
            order(node.right);
            }
        }

        /**后序遍历**/
    public void behind(Node node){
        if(node!=null){
            behind(node.left);
            behind(node.right);
            System.out.println(node.key+","+node.value);

        }
    }
    /**层序遍历（广度优先遍历）*/
public void levelOrder(Node node){
    Queue<Node> queue = new LinkedList();
    queue.offer(root);
     while (!queue.isEmpty()){
         Node node2 = queue.poll();
         System.out.println(node2.key+","+node2.value);
         if(node2.left!=null){
             queue.offer(node2.left);

         }
         if(node2.right!=null){
             queue.offer(node2.right);
         }

     }

}

/**获取最大值**/
public Node getMax(Node node){
    if(node.right==null){
        return  node;
    }
    return  getMax(node.right);
}
/**获取最小值**/
    public Node getMin(Node node) {
        if (node.left == null) {
            return node;
        }

        return getMin(node.left);
    }
/**移除最大值*/
public void removeMax(){
    if(root!=null){
        root= removeMax(root);
    }

}

  private Node removeMax(Node node){
    if(node.right==null){
            Node leftNode = node.left;
            node.left = null;
            count--;
            return leftNode;
        }
           node.right = removeMax(node.right);
          return node;
    }


    /**移除最小值**/
    public void removeMin(){
        if(root!=null){
            root= removeMin(root);
        }
    }

    private Node removeMin(Node node){
       if(node.left==null){
           Node rightNode = node.right;
           node.right=null;
           count--;
           return rightNode;
        }
        node.left =  removeMin(node.left);
           return node;
    }

    public  Node removeNode(Key key){

        return  removeNode(root,key);
    }

    private Node removeNode(Node node,Key key){

        if(node==null){
            return null;
        }
        if(node.key.compareTo(key)>0){
            return  node.left =  removeNode(node.left,key);
        }

        if(node.key.compareTo(key)<0){
            return node.right =  removeNode(node.right,key);
        }
        else{
            if(node.right==null){
                Node  leftNode = node.left;
                node.left=null;
                count--;
                return leftNode;
                }
            if(node.left==null){
               Node rightNode = node.right;
               node.right=null;
               node=rightNode;
               count--;
               return rightNode;

            }
            Node processorNode = getMin(node.right) ;
            processorNode.right = removeMin(node.right);
            processorNode.left = node.left;
            node.left = node.right = null;
            return  processorNode;
            }

    }
/*public void removeMax(){
    if(root!=null){
         removeMax(root);
    }

}

 private void removeMax(Node node){
     if(node.right.right==null && node.right!=null){
         Node leftNode = node.right.left;
         node.right  = leftNode;
         return;
     }
     removeMax(node.right);

 }*/


    /*public void  insert(Key key,Value value){

        if(root==null){
            root = new Node(key,value);
            count++;
        }
        else {

             insert(root,key,value);
        }

    }

    private void insert(Node node,Key key,Value value){
        if(node.key.equals(key)){
            return;
        }
        if(key.compareTo(node.key)>0){
            if(node.right==null){
                node.right = new Node(key,value);
                count++;
                return;
            }
            insert(node.right,key,value);
        }else if(key.compareTo(node.key)<0){
            if(node.left==null){
                node.left = new Node(key,value);
                count++;
                return;
            }
            insert(node.left,key,value);
        }


    }*/
 public static void main(String[] args) {
      BinarySearchTree binarySearchTree = new BinarySearchTree();
        binarySearchTree.insert(new Integer(240),5);
        binarySearchTree.insert(new Integer(108),5);
        binarySearchTree.insert(new Integer(300),5);
        binarySearchTree.insert(new Integer(60),5);
        binarySearchTree.insert(new Integer(206),5);
        binarySearchTree.insert(new Integer(260),5);
        binarySearchTree.insert(new Integer(347),5);
        binarySearchTree.insert(new Integer(205),5);
        binarySearchTree.insert(new Integer(257),5);
        binarySearchTree.insert(new Integer(266),5);
        binarySearchTree.insert(new Integer(320),5);
        binarySearchTree.insert(new Integer(356),5);
        binarySearchTree.insert(new Integer(350),5);
        binarySearchTree.insert(new Integer(349),5);


        System.out.println("先序遍历:");
        binarySearchTree.ahead(binarySearchTree.root);
        System.out.println("中序遍历:");
        binarySearchTree.order(binarySearchTree.root);
        System.out.println("后序遍历");
        binarySearchTree.behind(binarySearchTree.root);
        System.out.println("层序遍历");
        binarySearchTree.levelOrder(binarySearchTree.root);
        System.out.println("获取最大值");
        System.out.println(binarySearchTree.getMax(binarySearchTree.root).key);
       /* System.out.println("移除任意节点:");
        binarySearchTree.removeNode(new Integer(300));
        binarySearchTree.levelOrder(binarySearchTree.root);
        System.out.println("获取最小值");
        System.out.println(binarySearchTree.getMin(binarySearchTree.root).key);*/
        System.out.println("移除最大值层序遍历:");
        binarySearchTree.removeMax();
        binarySearchTree.levelOrder(binarySearchTree.root);
        System.out.println("移除最小值层序遍历:");
        binarySearchTree.removeMin();
        binarySearchTree.levelOrder(binarySearchTree.root);

    }
}
